
/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     struct ListNode *next;
* };
*/

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
	if (list1 == NULL || list2 == NULL){
		if (list1){
			return list1;
		}
		return list2;
	}

	struct ListNode newhead;         //定义一个新链表的头节点（作为返回链表的head）
	struct ListNode* cur = &newhead;   //cur指向新头节点

	while (list1 && list2)
	{
		if (list1->val <= list2->val){
			cur->next = list1;
			list1 = list1->next;
		}
		else{
			cur->next = list2;
			list2 = list2->next;
		}
		cur = cur->next;           //移到新链表的
	}
	// list1/list2 其中一个链表节点已经全部合并
	if (list1){          // list1还有节点
		cur->next = list1;
	}
	else{
		cur->next = list2;
	}
	return newhead.next;
}